// Copyright (c) 2005-2008, Simon Howard
// Permission to use, copy, modify, and/or distribute this software for any purpose
// with or without fee is hereby granted, provided that the above copyright notice
// and this permission notice appear in all copies.
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
// AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
// OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
// PERFORMANCE OF THIS SOFTWARE.

use std::ptr;

/// A double-ended queue (deque) implemented using a doubly linked list.
pub struct Deque<T> {
    head: *mut Node<T>,
    tail: *mut Node<T>,
}

/// A node in the doubly linked list.
struct Node<T> {
    data: T,
    prev: *mut Node<T>,
    next: *mut Node<T>,
}

impl<T> Deque<T> {
    /// Creates a new, empty deque.
    pub fn new() -> Self {
        Deque {
            head: ptr::null_mut(),
            tail: ptr::null_mut(),
        }
    }

    /// Checks if the deque is empty.
    pub fn is_empty(&self) -> bool {
        self.head.is_null()
    }

    /// Adds an element to the front of the deque.
    pub fn push_head(&mut self, data: T) {
        let new_node = Box::into_raw(Box::new(Node {
            data,
            prev: ptr::null_mut(),
            next: self.head,
        }));

        if self.head.is_null() {
            self.tail = new_node;
        } else {
            unsafe { (*self.head).prev = new_node };
        }

        self.head = new_node;
    }

    /// Removes and returns the element from the front of the deque.
    /// Returns `None` if the deque is empty.
    pub fn pop_head(&mut self) -> Option<T> {
        if self.head.is_null() {
            return None;
        }

        let node = unsafe { Box::from_raw(self.head) };
        self.head = node.next;

        if self.head.is_null() {
            self.tail = ptr::null_mut();
        } else {
            unsafe { (*self.head).prev = ptr::null_mut() };
        }

        Some(node.data)
    }

    /// Returns a reference to the element at the front of the deque without removing it.
    /// Returns `None` if the deque is empty.
    pub fn peek_head(&self) -> Option<&T> {
        if self.head.is_null() {
            None
        } else {
            unsafe { Some(&(*self.head).data) }
        }
    }

    /// Adds an element to the back of the deque.
    pub fn push_tail(&mut self, data: T) {
        let new_node = Box::into_raw(Box::new(Node {
            data,
            prev: self.tail,
            next: ptr::null_mut(),
        }));

        if self.tail.is_null() {
            self.head = new_node;
        } else {
            unsafe { (*self.tail).next = new_node };
        }

        self.tail = new_node;
    }

    /// Removes and returns the element from the back of the deque.
    /// Returns `None` if the deque is empty.
    pub fn pop_tail(&mut self) -> Option<T> {
        if self.tail.is_null() {
            return None;
        }

        let node = unsafe { Box::from_raw(self.tail) };
        self.tail = node.prev;

        if self.tail.is_null() {
            self.head = ptr::null_mut();
        } else {
            unsafe { (*self.tail).next = ptr::null_mut() };
        }

        Some(node.data)
    }

    /// Returns a reference to the element at the back of the deque without removing it.
    /// Returns `None` if the deque is empty.
    pub fn peek_tail(&self) -> Option<&T> {
        if self.tail.is_null() {
            None
        } else {
            unsafe { Some(&(*self.tail).data) }
        }
    }
}

impl<T> Drop for Deque<T> {
    fn drop(&mut self) {
        while let Some(_) = self.pop_head() {}
    }
}

#[cfg(test)]
mod tests {
    use super::Deque;

    #[test]
    fn test_push_pop_head() {
        let mut deque: Deque<i32> = Deque::new();
        deque.push_head(1);
        deque.push_head(2);
        assert_eq!(deque.pop_head(), Some(2));
        assert_eq!(deque.pop_head(), Some(1));
        assert_eq!(deque.pop_head(), None);
    }

    #[test]
    fn test_push_pop_tail() {
        let mut deque: Deque<i32> = Deque::new();
        deque.push_tail(1);
        deque.push_tail(2);
        assert_eq!(deque.pop_tail(), Some(2));
        assert_eq!(deque.pop_tail(), Some(1));
        assert_eq!(deque.pop_tail(), None);
    }

    #[test]
    fn test_peek_head() {
        let mut deque: Deque<i32> = Deque::new();
        deque.push_head(1);
        assert_eq!(deque.peek_head(), Some(&1));
        deque.push_head(2);
        assert_eq!(deque.peek_head(), Some(&2));
    }

    #[test]
    fn test_peek_tail() {
        let mut deque: Deque<i32> = Deque::new();
        deque.push_tail(1);
        assert_eq!(deque.peek_tail(), Some(&1));
        deque.push_tail(2);
        assert_eq!(deque.peek_tail(), Some(&2));
    }

    #[test]
    fn test_is_empty() {
        let mut deque: Deque<i32> = Deque::new();
        assert!(deque.is_empty());
        deque.push_head(1);
        assert!(!deque.is_empty());
        deque.pop_head();
        assert!(deque.is_empty());
    }
}
